package cn.corffen.test.algorithm.leetcode.easy.linked;

import cn.corffen.test.algorithm.leetcode.easy.ListNode;

import java.util.ArrayList;
import java.util.List;

public class LinkedDemo {
    public static void main(String[] args) {

    }

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        int x = 0;
        ListNode temp = new ListNode(0);
        temp.next = head;
        ListNode first = head;
        while (first != null) {
            x++;
            first = first.next;
        }
        x = x - n;
        first = temp;
        while (x > 0) {
            x--;
            first = first.next;
        }
        first.next = first.next.next;
        return temp.next;
    }

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode tempNext = curr.next;
            curr.next = pre;
            pre = curr;
            curr = tempNext;
        }
        return pre;
    }

    public ListNode reverseList2(ListNode head) {
        ListNode curr = head;
        ListNode pre = null;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prevHead = new ListNode(-1);
        ListNode prev = prevHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return prevHead.next;
    }

    public boolean isPalindrome(ListNode head) {
        List<Integer> values = new ArrayList<>();
        while (head != null) {
            values.add(head.val);
            head = head.next;
        }
        int start = 0;
        int end = values.size() - 1;
        while (start < end) {
            if (!values.get(start).equals(values.get(end))) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    public boolean isPalindrome1(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode firstHalf = halfEnd(head);
        //翻转后半部分的ListNode
        ListNode secondHalf = reverseList(firstHalf.next);
        //注意p1要指向head
        ListNode p1 = head;
        //p2指向后半部分的ListNode
        ListNode p2 = secondHalf;
        boolean result = true;
        //遍历p2,依次比较二者的值.
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        //再次的翻转后半部分,就将后半部分的ListNode还原为原来的顺序了.
        firstHalf.next = reverseList(secondHalf);
        return result;
    }

    /**
     * 快慢指针 当快指针结束时
     * 满指针到达一半.此时返回慢指针
     * 那么 slow.next就是后面一半的ListNode
     * 使用栈内赋值,不会修改形参.
     *
     * @param head
     * @return
     */
    public ListNode halfEnd(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 利用快慢指针来遍历链表
     * 如果有环,二者必然会相遇,此时快慢相等 返回true
     * 而如果快指针遍历到尾部了,那么说明没有环
     * 尾部的条件是fast==null || fast.next = null.
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != slow) {
            if (fast == null || fast.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}
